import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class BinaryTreeSolution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    int maxDiameter = 0;


    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        getMaxDepthForMaxDiameter(root);
        return maxDiameter;
    }

    private int getMaxDepthForMaxDiameter(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxDepth = getMaxDepthForMaxDiameter(root.left);
        int rightMaxDepth = getMaxDepthForMaxDiameter(root.right);
        maxDiameter = Math.max(leftMaxDepth + rightMaxDepth, maxDiameter);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> list = new ArrayList<>();
        traverseForFlatten(root, list);
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i + 1);
        }
    }

    private void traverseForFlatten(TreeNode root, List<TreeNode> list) {
        if (root == null)
            return;
        list.add(root);
        traverseForFlatten(root.left, list);
        traverseForFlatten(root.right, list);
    }


    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length - 1);
    }

    private TreeNode construct(int[] nums, int left, int right) {
        if (left > right)
            return null;
        int maxIndex = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[maxIndex])
                maxIndex = i;
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = construct(nums, left, maxIndex - 1);
        root.right = construct(nums, maxIndex + 1, right);
        return root;
    }


    public TreeNode buildTreeByPreAndIn(int[] preorder, int[] inorder) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        int size = preorder.length;
        int inorderIndex = 0;
        for (int i = 1; i < size; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.empty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.peek();
                    stack.pop();
                    ++inorderIndex;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Stack<TreeNode> stack = new Stack<>();
        int size = postorder.length;
        TreeNode root = new TreeNode(postorder[size - 1]);
        stack.push(root);
        int inorderIndex = size -1;
        for (int i = size - 2; i >= 0; --i) {
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            } else {
                while (!stack.empty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.peek();
                    stack.pop();
                    --inorderIndex;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }


    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int size = preorder.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < size; i++) {
            map.put(postorder[i], i);
        }

        class Inner {
            TreeNode helper(int preLeft, int preRight, int postLeft, int postRight) {
                if (preLeft > preRight)
                    return null;

                int leftCount = 0;
                if (preLeft < preRight)
                    leftCount = map.get(preorder[preLeft + 1]) - postLeft + 1;

//            The left child in posttraversal is postRight - 1
                return new TreeNode(preorder[preLeft],
                        helper(preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1),
                        helper(preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1));
            }
        }

        return new Inner().helper(0, size - 1, 0, size - 1);
    }

    Map<String, AbstractMap.SimpleEntry<TreeNode, Integer>> seen = new HashMap<>();
    Set<TreeNode> repeat = new HashSet<>();
    int idx = 0;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        class Inner {
            int dfs(TreeNode node) {
                if (node == null)
                    return 0;
                int[] tri = {node.val, dfs(node.left), dfs(node.right)};
                String hash = Arrays.toString(tri);
                if (seen.containsKey(hash)) {
                    AbstractMap.SimpleEntry<TreeNode, Integer> pair = seen.get(hash);
                    repeat.add(pair.getKey());
                    return pair.getValue();
                } else {
                    seen.put(hash, new AbstractMap.SimpleEntry<>(node, ++idx));
                    return idx;
                }
            }
        }

        new Inner().dfs(root);
        return new ArrayList<>(repeat);
    }

    public static void main(String[] args) {
        String str = ",123,234,,678,";
        String[] split = str.split(",");
        System.out.println("");
    }
}


public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        rserialize(root, builder);
        return builder.toString();
    }

    private void rserialize(TreeNode root, StringBuilder builder) {
        if (root == null) {
            builder.append("None,");
        } else {
            builder.append(root.val);
            builder.append(',');
            rserialize(root.left, builder);
            rserialize(root.right, builder);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // split使用正则分割，若字符串最后一个字符为分割符，则生成的数组最后一项不会是空字符串
        String[] strs = data.split(",");
        LinkedList<String> list = new LinkedList<>(Arrays.asList(strs));
        return rDeserialize(list);
    }

    private TreeNode rDeserialize(LinkedList<String> list) {
        if ("None".equals(list.getFirst())) {
            list.removeFirst();
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(list.getFirst()));
        list.removeFirst();
        root.left = rDeserialize(list);
        root.right = rDeserialize(list);
        return root;
    }
}
